package medium;

public class Problem_05_LIS {

    public static int[] lis1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        int[] dp = getdp1(arr);
        return generateLIS(arr, dp);
    }
    //dp中放的是，对应数组中每个元素为输出序列的最后一个值时的最大长度
//方法一：O(n^2)复杂度，具体思路是：两层循环，外层为i时，内从从0到i,依次判断，当加入 arr[i]的值后，更新dp中最长子序列的长度，最长
//子序列更新，依赖于i前面的dp中的数组值，若是arr[i]比i之前的某个位置上的的数要大，则通过max(dp[i], dp[j] + 1);来
//更新第i位上的值。
    public static int[] getdp1(int[] arr) {
        int[] dp = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        return dp;
    }

    //根据 dp 数组的值生成要打印的数组，作为最后结果的输出，
    public static int[] generateLIS(int[] arr, int[] dp) {
        int len = 0;
        int index = 0;
        for (int i = 0; i < dp.length; i++) {
            if (dp[i] > len) {
                len = dp[i];
                index = i;
            }
        }
        int[] lis = new int[len];
        lis[--len] = arr[index];
        for (int i = index; i >= 0; i--) {
            if (arr[i] < arr[index] && dp[i] == dp[index] - 1) {
                lis[--len] = arr[i];
                index = i;
            }
        }
        return lis;
    }

    public static int[] lis2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        int[] dp = getdp2(arr);
        return generateLIS(arr, dp);
    }

    //方法二，时间复杂度为O(N*logN)，这个时间复杂度具体体现在一个for循环里套了一个二分查找
//dp中放的是，对应数组中每个元素为输出序列的最后一个值时的最大长度
//ends数组作为一个辅助数组，存放的是有效区的数值，ends[i]的含义是：
//当遍历到当前的数时，ends[i]表示的是，遍历到当前时刻，长度为i+1的子序列中的末尾元素值
//每次更新的是长度为i+1子序列的末尾元素的值，那么，可以通过二分法查找每个当前遍历到的元素在ends中应该所处的位置
//然后更新对应的位置上的元素值，然后根据i+1，就可以知道，当前元素作为子序列的末尾元素时，前面有几个数了（i）
//程序中的right值记录的是，有效区数组ends的长度，l为左边界，r为右边界，m为中间值
    public static int[] getdp2(int[] arr) {
        int[] dp = new int[arr.length];
        int[] ends = new int[arr.length];
        ends[0] = arr[0];
        dp[0] = 1;
        int right = 0;
        int l = 0;
        int r = 0;
        int m = 0;
        for (int i = 1; i < arr.length; i++) {
            l = 0;
            r = right;
            while (l <= r) {
                m = (l + r) / 2;
                if (arr[i] > ends[m]) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
            right = Math.max(right, l);  //更新有效区数组的边界值，若是所有的元素都小于当前的元素，则数组值往外扩充一个
            ends[l] = arr[i];
            dp[i] = l + 1;
        }
        return dp;
    }

    // for test
    public static void printArray(int[] arr) {
        for (int i = 0; i != arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = { 10,9,2,5,3,7,101,18};
        printArray(arr);
        printArray(lis1(arr));
        printArray(lis2(arr));

    }
}